package org.laizili.solution.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/koko-eating-bananas/">875. 爱吃香蕉的珂珂</a>
 * <p>
 * tags: 二分搜索应用题;<br/>
 * notes: 二分搜索的标志: 在有序空间搜索答案, 关键是找到搜索空间的上界和下界, 及搜索准则(如何缩小搜索范围), 尤其注意 <b>边界条件</b>
 * <p>
 * leetcode submitted time: 2022年6月7日10:05:44
 */
public class Problem875 {
    private static class Solution {
        public int minEatingSpeed(int[] piles, int h) {
            int left = 1;
            int right = Arrays.stream(piles).max().getAsInt();
            while (left <= right) {
                int mid = (left + right) / 2;
                int cnt = 0;
                for (int pile : piles) {
                    if (pile < mid) {
                        ++cnt;
                    } else {
                        cnt += Math.ceil(((double) pile / mid));
                    }
                }
                if (cnt > h) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    }

    public static void main(String[] args) {
        // official test case
        Solution solution = new Solution();
        System.out.println(solution.minEatingSpeed(new int[]{3, 6, 7, 11}, 8));
        System.out.println(solution.minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 5));
        System.out.println(solution.minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 6));
        // my test case
        System.out.println(solution.minEatingSpeed(new int[]{8}, 2));
    }
}
